package JavaBase.ArrayTest;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author：coinyang
 * @Project：JavaTest
 * @name：质数
 * @Date：2023/8/3 17:47
 */
public class 质数 {
    public static void main(String[] args) {
        int n = 100;  // 输入一个整数 n
        List<Integer> primes = getPrimeNumbers(n);
        System.out.println("小于 " + n + " 的所有质数为：" + primes);
    }

    private static List<Integer> getPrimeNumbers(int n) {
        List<Integer> primes = new ArrayList<>();

        boolean[] isPrime = new boolean[n];  // 定义一个长度为 n 的 boolean 数组，默认初始值均为 true
        for (int i = 2; i < n; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                primes.add(i);  // 如果当前数是质数，则将其加入结果列表

                for (int j = i + i; j < n; j += i) {
                    isPrime[j] = false;  // 将当前质数的倍数置为 false
                }
            }
        }

        return primes;
    }
}
